package com.cqs.leetcode;


/**
 * Created by cqs on 2018/4/5.
 */
public class NumberOfIslands3 {
    private int row;
    private int cell;
    private char[][] grid;
    private int count;
    private int[] us;

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        this.grid = grid;
        row = grid.length;
        cell = grid[0].length;
        count = 0;
        us = new int[row * cell];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < cell; j++) {
                if (us[index(i,j)]==0 && grid[i][j] == '1') {
                    //System.out.println(i + "\t" + j);
                    dfs(i, j);
                    ++count;
                }
            }
        }
        return count;
    }

    private void dfs(int i, int j) {

        if (us[index(i, j)] == 1) return;

        us[index(i, j)] = 1;
        if (i > 0 && grid[i - 1][j] == '1') {
            dfs(i - 1, j);
        }

        if (i < row - 1 && grid[i + 1][j] == '1') {
            dfs(i + 1, j);
        }


        if (j < cell - 1 && grid[i][j + 1] == '1') {
            dfs(i, j + 1);
        }

        if (j > 0 && grid[i][j - 1] == '1') {
            dfs(i, j - 1);
        }

    }

    private int index(int i, int j) {
        return i * cell + j;
    }


}
